나무 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 종류
- 4.1. 유향 그래프
- 4.2. 루트 트리 (Rooted Tree)
5. 역사
참조

1. 개요

나무 그래프는 점(정점)과 점들을 연결하는 선(변)으로 구성된 그래프의 한 종류이다. 순환이 없고, 임의의 두 정점 사이의 경로가 유일하게 존재하는 연결 그래프를 나무 그래프라고 정의하며, 숲 그래프, 잎 꼭짓점, 내부 꼭짓점 등의 관련 용어가 있다. 나무 그래프는 숲 그래프이며, 이분 그래프이자 평면 그래프이다. 나무 그래프의 수, 프뤼퍼 열, 케일리 공식과 같은 수학적 개념과 연관되어 있으며, 경로 그래프, 별 나무, 애벌레 나무 등 다양한 종류가 존재한다. 1860년 카를 빌헬름 보르하르트가 케일리 공식을 최초로 증명했으며, 1918년 에른스트 파울 하인츠 프뤼퍼는 프뤼퍼 열을 도입했다.

더 읽어볼만한 페이지

그래프 - 매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다.
그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.

나무 그래프
그래프 이론
정의	무향, 연결되고 사이클이 없는 그래프
다른 이름	아치 없는 연결 그래프, 사이클 없는 연결 그래프, 연결된 사이클 없는 그래프
속성	꼭짓점이 v개인 트리는 v − 1개의 변을 가진다. 꼭짓점이 v개인 그래프는 다음 조건들이 동치이다. 그래프는 트리이다. 그래프는 사이클이 없으며, v − 1개의 변을 가진다. 그래프는 연결되어 있으며, v − 1개의 변을 가진다. 그래프의 두 꼭짓점 사이에는 정확히 하나의 경로가 존재한다. 그래프는 연결되어 있지만, 하나의 변이라도 제거하면 연결이 끊어진다. 그래프는 사이클이 없지만, 임의의 두 꼭짓점 사이에 변을 추가하면 사이클이 생긴다.
채색수	v > 1인 경우 2
수학
정의	무향, 연결이고 회로가 없는 그래프
성질	n개의 꼭짓점을 가진 나무는 n − 1개의 변을 갖는다. 그래프가 나무일 필요충분조건은, 그래프에 회로가 없고, n − 1개의 변을 갖는 것이다. 그래프가 나무일 필요충분조건은, 그래프가 연결되어 있고, n − 1개의 변을 갖는 것이다. 그래프가 나무일 필요충분조건은, 임의의 두 꼭짓점 사이에 정확히 하나의 경로가 존재하는 것이다. 그래프가 나무일 필요충분조건은, 그래프가 연결되어 있지만, 임의의 변을 제거하면 연결이 끊어지는 것이다. 그래프가 나무일 필요충분조건은, 그래프에 회로가 없지만, 임의의 두 꼭짓점 사이에 변을 추가하면 회로가 생기는 것이다.

2. 정의

그래프는 점(정점, vertex)과 점들을 연결하는 선(변, edge)으로 구성된다. 그래프 $T$ 에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 $T$ 를 '''나무 그래프'''라고 한다.

$T$ 는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다).
임의의 두 꼭짓점 $v_1,v_2\in V(T)$ 에 대하여, $v_1$ 과 $v_2$ 사이의 경로가 정확히 하나 존재한다.
$T$ 는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.)
하나 이상의 꼭짓점을 가지며, 임의의 변 $e\in\operatorname E(T)$ 을 지운 그래프 $T-e$ 는 연결 그래프가 아니다.

나무 그래프

T

의 '''잎 꼭짓점'''(leaf vertex|리프 버텍스^영어)은 차수가 1인 꼭짓점이며, '''내부 꼭짓점'''(internal vertex^영어)은 차수가 2 이상인 꼭짓점이다.

2. 1. 숲 그래프 (Forest Graph)

숲 그래프(forest graph|포리스트 그래프^영어)는 다음 조건들을 만족하는 그래프이다.

T는 길이 3 이상의 순환을 갖지 않는다.
임의의 두 꼭짓점 v₁, v₂ ∈ V(T)에 대하여, v₁과 v₂ 사이의 경로의 수는 1 이하이다.
T는 완전 그래프 K₃를 마이너로 갖지 않는다.
T는 단일 연결 공간이다.

숲은 무방향 비순환 그래프, 또는 동등하게는 그래프의 분리된 합인 그래프이다. 자명하게 숲의 각 연결 요소는 트리이다. 특별한 경우로, 0차 그래프(0개의 트리로 구성된 숲), 단일 트리, 그리고 엣지가 없는 그래프는 숲의 예시이다.

모든 트리에서 총 정점 수에서 총 엣지 수를 빼서 숲 안에 있는 트리의 수를 쉽게 셀 수 있다. 즉, ''V'' − ''E'' = 숲의 트리 수.

2. 2. 나무 그래프 (Tree Graph)

그래프

T

에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프

T

를 '''나무 그래프'''라고 한다.

$T$ 는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다).
임의의 두 꼭짓점 $v_1,v_2\in V(T)$ 에 대하여, $v_1$ 과 $v_2$ 사이의 경로가 정확히 하나 존재한다.
$T$ 는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.)
하나 이상의 꼭짓점을 가지며, 임의의 변 $e\in\operatorname E(T)$ 을 지운 그래프 $T-e$ 는 연결 그래프가 아니다.

나무 그래프

T

의 '''잎 꼭짓점'''(leaf vertex|리프 버텍스^영어)은 차수가 1인 꼭짓점이며, '''내부 꼭짓점'''(internal vertex^영어)은 차수가 2 이상인 꼭짓점이다.

트리는 다음의 등가 조건을 만족하는 무방향 그래프이다.

연결 그래프이고 비순환적이다(사이클을 포함하지 않는다).
비순환적이며, 어떤 변이 추가되면 단순 사이클이 형성된다.
연결되어 있지만, 단일 변이 제거되면 분리된다.
연결되어 있으며 완전 그래프 은 마이너가 아니다.
두 정점은 고유한 단순 경로로 연결될 수 있다.

만약 유한개의 정점을 가지고, 예를 들어 개의 정점을 가진다면, 위의 진술들은 다음 조건과도 같다.

연결되어 있고 개의 변을 가진다.
연결되어 있으며 의 모든 부분 그래프는 0개 또는 1개의 인접한 변을 가진 정점을 하나 이상 포함한다. (즉, 연결되어 있고 1-퇴화이다.)
단순 사이클이 없고 개의 변을 가진다.

그래프 이론의 다른 곳과 마찬가지로, 차수-영 그래프 (정점이 없는 그래프)는 일반적으로 트리로 간주되지 않는다. 그래프로서는 비어있기 때문에 연결되어 있지만 (두 정점은 경로로 연결될 수 있음), 비어있지 않은 트리와 달리 대수적 위상수학에서 0-연결 (또는 심지어 (−1)-연결)이 아니고, "변보다 정점이 하나 더 많다"는 관계를 위반한다. 그러나 0개의 트리로 구성된 숲으로 간주할 수 있다.

내부 정점은 차수가 2 이상인 정점이다. 마찬가지로, 외부 정점(또는 외정점, 단말 정점 또는 잎)은 차수가 1인 정점이다. 트리의 분기 정점은 차수가 3 이상인 정점이다.^[15]

기약 트리 (또는 직렬 축소 트리)는 차수가 2인 정점이 없는 트리이다.

개의 점으로 이루어진 그래프 에 대해 다음은 동치이다.

는 트리이다.
에는 사이클이 없고, 개의 변을 가진다.
는 연결되어 있으며, 개의 변을 가진다.
는 연결되어 있으며, 모든 변은 단절선이다.
의 임의의 두 점을 잇는 경로가 정확히 하나 있다.
에 사이클은 없지만, 새로운 변을 추가하면 반드시 사이클이 하나 생긴다.

2. 3. 관련 용어

그래프에서 '''잎 꼭짓점'''(leaf vertex|리프 버텍스^영어)은 차수가 1인 꼭짓점이며, '''내부 꼭짓점'''(internal vertex^영어)은 차수가 2 이상인 꼭짓점이다. '''기약 트리'''(series-reduced tree^영어)는 차수가 2인 정점이 없는 트리이다.

3. 성질

숲 그래프 $T$ 에 대하여 다음이 성립한다.

$|\operatorname V(T)| = |\operatorname E(T)| + |\operatorname{Conn}(T)|$

여기서

$|\operatorname V(T)|$ 는 $T$ 의 꼭짓점의 수이다.
$|\operatorname E(T)|$ 는 $T$ 의 변의 수이다.
$|\operatorname Conn(T)|$ 는 $T$ 의 연결 성분의 수이다.

특히, 나무 그래프는 연결 성분이 하나이므로,

|\operatorname V(T)|=|\operatorname E(T)|+1

이다.

모든 숲 그래프는 이분 그래프이자 평면 그래프이다. 모든 연결 그래프는 신장 트리를 갖는다.

그래프 이론에서, 트리는 다음 조건을 만족하는 무방향 그래프

G

이다.

$G$ 는 연결 그래프이고 비순환적이다(사이클을 포함하지 않는다).
$G$ 는 비순환적이며, 어떤 변을 추가하면 단순 사이클이 형성된다.
$G$ 는 연결되어 있지만, $G$ 에서 변 하나를 제거하면 분리된다.
$G$ 는 연결되어 있으며 완전 그래프 $K_3$ 은 $G$ 의 마이너가 아니다.
$G$ 의 두 정점은 유일한 단순 경로로 연결된다.

G

가 유한개의 정점, 즉

n

개의 정점을 가진다면, 위 조건들은 다음과 동치이다.

$G$ 는 연결되어 있고 $n-1$ 개의 변을 가진다.
$G$ 는 연결되어 있으며 $G$ 의 모든 부분 그래프는 0개 또는 1개의 인접한 변을 가진 정점을 하나 이상 포함한다. (즉, $G$ 는 연결되어 있고 1-퇴화이다.)
$G$ 는 단순 사이클이 없고 $n-1$ 개의 변을 가진다.

차수-영 그래프(정점이 없는 그래프)는 일반적으로 트리로 간주되지 않는다.
내부 정점(또는 내정점)은 차수가 2 이상인 정점이다. 외부 정점(또는 외정점, 단말 정점 또는 잎)은 차수가 1인 정점이다. 트리의 분기 정점은 차수가 3 이상인 정점이다.^[15]
기약 트리(또는 직렬 축소 트리)는 차수가 2인 정점이 없는 트리이다.

총 정점 수에서 총 변의 수를 빼면 숲 안에 있는 트리의 수를 쉽게 알 수 있다. 즉, 숲의 트리 수는

V - E

이다.

모든 트리는 이분 그래프이다. 그래프는 홀수 길이의 사이클을 포함하지 않는 경우에만 이분 그래프이다. 트리는 사이클을 전혀 포함하지 않으므로 이분 그래프이다.
가산 개의 정점만 있는 모든 트리는 평면 그래프이다.
모든 연결 그래프 ''G''는 ''G''의 모든 정점을 포함하고 그 변이 ''G''의 변인 신장 트리를 갖는다.
$n>1$ 인 ''n''개의 정점을 가진 모든 유한 트리는 최소 두 개의 단말 정점(잎)을 갖는다. 잎의 수는 최소 최대 정점 차수이다.
트리의 세 정점에 대해, 그들 사이의 세 경로는 정확히 하나의 공통 정점을 갖는다. 모든 트리는 중앙값 그래프이다.
모든 트리는 하나의 정점 또는 두 개의 인접한 정점으로 구성된 중심을 갖는다. 마찬가지로, 모든 ''n''-정점 트리는 하나의 정점 또는 두 개의 인접한 정점으로 구성된 중심점을 갖는다.
트리의 최대 클릭은 정확히 그 변이며, 트리의 클래스가 클릭이 적다는 것을 의미한다.

n

개의 점으로 이루어진 그래프

T

에 대해 다음은 동치이다.

$T$ 는 트리이다.
$T$ 에는 사이클이 없고, $n-1$ 개의 변을 가진다.
$T$ 는 연결되어 있으며, $n-1$ 개의 변을 가진다.
$T$ 는 연결되어 있으며, 모든 변은 단절선이다.
$T$ 의 임의의 두 점을 잇는 경로가 정확히 하나 있다.
$T$ 에 사이클은 없지만, 새로운 변을 추가하면 반드시 사이클이 하나 생긴다.

나무

T

는 다음과 같은 성질을 가진다.

$T$ 의 두 점을 잇는, $T$ 에 포함되지 않는 변 $e$ 에 대해, $T+e$ 에는 $e$ 를 지나는 단 하나의 사이클이 존재하며, 이 사이클 위의 임의의 변 $f$ 에 대해 $T + e - f$ 는 나무가 된다.
꼭짓점이 2개 이상인 나무에는 최소 2개의 단말점(terminal vertex)이 있다. 또한, 단말점은 차수 1의 점이다.

3. 1. 나무 그래프의 수

n개의 꼭짓점을 갖는 나무 그래프의 동형류의 수는 다음과 같다 (n=0, 1, 2, ...).

: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ...^[22]

n개의 꼭짓점을 갖는 숲 그래프의 동형류의 수는 다음과 같다 (n=0, 1, 2, ...).

: 1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, ...

3. 2. 프뤼퍼 열 (Prüfer Sequence)

정렬 순서가 주어진 유한 나무 그래프

T

에 대하여, 프뤼퍼 열은 다음과 같이 재귀적으로 정의되는 꼭짓점들의 열

(y_i)

이다.

먼저, 다음과 같은 꼭짓점 열

x_i

를 정의한다.

각 단계에서, $T$ 에서 이미 선택된 꼭짓점들을 제외한 나머지 꼭짓점들 중 잎 꼭짓점을 찾는다.
잎 꼭짓점들 중에서 정렬 순서에 따라 가장 작은 꼭짓점을 $x_i$ 로 선택한다.

이제,

x_i

를 이용하여 다음과 같이 꼭짓점 열

y_i

를 정의한다.

각 단계에서, $T$ 에서 이미 선택된 꼭짓점들을 제외한 그래프에서, $x_i$ 와 인접한 유일한 꼭짓점을 $y_i$ 로 선택한다.
만약 인접한 꼭짓점이 없다면, 열은 종료된다.

유한 나무 그래프의 경우,

y_i

의 길이는

n-2

이다. 마지막에는 꼭짓점이 하나만 남기 때문이다. 이렇게 얻어진

(y_i)

를

T

의 '''프뤼퍼 열'''(Prüfer列, Prüfer sequence^영어)이라고 한다.

프뤼퍼 열은 다음과 같은 성질을 갖는다.

유한 나무 그래프	프뤼퍼 열
꼭짓점의 수	프뤼퍼 열의 길이 + 2
변의 수	프뤼퍼 열의 길이 + 1
잎 꼭짓점	프뤼퍼 열에 등장하지 않는 꼭짓점
내부 꼭짓점	프뤼퍼 열에 등장하는 꼭짓점
꼭짓점의 차수	프뤼퍼 열에 등장하는 횟수 + 1

모든 유한 나무 그래프는 그 프뤼퍼 열로부터 복원할 수 있다. 알고리즘은 다음과 같다.

# 각 꼭짓점 $v$ 에 대해, 프뤼퍼 열에 등장하는 횟수 + 1을 값으로 갖는 변수 $\mathtt{d}_v$ 를 설정한다.

# 프뤼퍼 열의 첫 번째 꼭짓점 $y_0$ 에 대하여, $\mathsf{d}_v=1$ 인 가장 작은 꼭짓점 $v$ 를 찾는다.

## 변 $(v,y_0)$ 를 그래프에 추가한다.

## $\mathtt{d}_{y_0}$ 과 $\mathtt{d}_v$ 를 각각 1씩 감소시킨다.

# 프뤼퍼 열의 나머지 꼭짓점들에 대해 위 단계를 반복한다.

# 이 과정이 끝나면, $\mathtt{d}_v=1$ 인 꼭짓점이 두 개 남는다. 이 둘 사이에 변을 추가한다.

다음 그래프를 예시로 들어보자.

# 잎 꼭짓점은

\{1,2,3,6\}

이고, 이 가운데 최소는 1이다. 1은 4에 연결되어 있으므로

x_0=1

,

y_0=4

이다. 꼭짓점 1을 제거한다.

#

T\setminus\{1\}

의 잎 꼭짓점은

\{2,3,6\}

이고, 이 가운데 최소는 2이다. 2는 4에 연결되어 있으므로

x_1=2

,

y_1=4

이다. 꼭짓점 2를 제거한다.

#

T\setminus\{1,2\}

의 잎 꼭짓점은

\{3,6\}

이고, 이 가운데 최소는 3이다. 3은 4에 연결되어 있으므로

x_2=3

,

y_2=4

이다. 꼭짓점 3을 제거한다.

#

T\setminus\{1,2,3\}

의 잎 꼭짓점은

\{4,6\}

이고, 이 가운데 최소는 4이다. 4는 5에 연결되어 있으므로

x_3=4

,

y_3=5

이다. 꼭짓점 4를 제거한다.

#

T\setminus\{1,2,3,4\}

의 잎 꼭짓점은

\{5,6\}

이고, 이 가운데 최소는 5이다. 5는 6에 연결되어 있지만, 6도 잎 꼭짓점이므로 프뤼퍼 열은 끝난다.

따라서 프뤼퍼 열은

(4,4,4,5)

이다.

3. 3. 케일리 공식 (Cayley's Formula)

n개의 레이블이 붙은 서로 다른 나무 그래프의 개수는

n^{n-2}

개이다. (단, n ≥ 2)

'''증명:'''

꼭짓점 집합

V

에 임의의 정렬 순서를 부여하면,

V

위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응되며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는

n^{n-2}

이다.^[25]

4. 종류

나무 그래프는 다양한 종류로 분류될 수 있다.
유향 그래프무향 나무는 임의의 점을 뿌리(루트)로 정할 수 있지만, 유향 나무는 뿌리인 점이 하나만 존재한다. 변의 방향은 뿌리에서 잎으로 향하거나, 잎에서 뿌리로 향하는 두 가지 경우가 있다. 두 방향이 섞이면 사이클이 생기기 때문에 혼합은 불가능하다.^[23]

사이클이 없는 유향 그래프는 유향 비순환 그래프(DAG)이다.^[24] 유향 나무는 연결된 유향 비순환 그래프이지만, 연결된 유향 비순환 그래프가 모두 유향 나무는 아니다. DAG는 자손이나 부모를 공유하는 경우가 있어 나무가 아닐 수 있다.
루트 트리 (Rooted Tree)루트 트리는 하나의 정점을 루트(root)로 지정한 트리이다.^[19] 루트 트리의 간선에는 루트에서 멀어지거나 루트를 향하는 자연스러운 방향을 부여할 수 있는데, 전자를 '아보레스cent' 또는 '아웃 트리', 후자를 '안티 아보레스cent' 또는 '인 트리'라고 한다.

루트 트리는 가계도에 비유하여 용어를 사용하기도 한다.

어떤 점과 변으로 연결되어 있고, 이 점보다 루트에 더 가까우면, 이 점은 해당 점의 '''부모''', 해당 점은 이 점의 '''자식'''이 된다.
두 점이 공통 부모를 가지면, 두 점은 '''형제'''이다.
두 점 중 한 점과 루트를 잇는 경로 상에 다른 한 점이 있으면, 경로 상에 있는 점은 다른 점의 '''선조''', 다른 점은 경로 상에 있는 점의 '''자손'''이 된다.

루트 트리에 관한 추가 용어는 다음과 같다.

자식이 없는 점은 '''잎'''이다.
각 변의 길이를 1로 할 때, 점과 루트 간 경로 길이는 그 점의 '''높이'''이다. 루트에서 가장 긴 경로 길이를 가진 점까지의 길이는 트리의 '''높이'''이다.

루트 트리에서 정점의 ''부모''는 루트로 가는 경로에서 해당 정점에 연결된 정점이다. 모든 정점은 고유한 부모를 가지며 루트는 부모가 없다. 정점의 ''자식''은 해당 정점이 부모인 정점이다. ''조상''은 부모이거나 부모의 조상인 정점이고, ''자손''은 자식이거나 자식의 자손인 정점이다. ''형제''는 부모를 공유하는 다른 정점이다. ''리프''는 자식이 없는 정점이고, ''내부 정점''은 리프가 아닌 정점이다.

정점의 ''높이''는 해당 정점에서 리프까지의 가장 긴 하향 경로의 길이이고, 트리의 ''높이''는 루트의 높이이다. 정점의 ''깊이''는 루트까지의 경로의 길이이다. 트리의 깊이는 모든 정점의 최대 깊이이며, AVL 트리를 조작하는 데 필요하다. 루트의 깊이는 0, 리프의 높이는 0, 단일 정점만 있는 트리의 깊이와 높이는 0이다. 빈 트리의 깊이와 높이는 −1이다.

자연수 n에 대해, 잎이 아닌 각 점의 자식 수가 항상 n인 나무를 '''n분 나무'''(n-ary tree)라고 한다. 이진 트리는 여러 알고리즘과 관련된 자료 구조이다.

''-진 트리''(음이 아닌 정수 k)는 각 정점이 최대 k개의 자식을 갖는 루트 트리이다.^[19] 2-진 트리는 ''이진 트리'', 3-진 트리는 ''삼진 트리''라고도 한다.

'''순서 트리''' ('''평면 트리''' 또는 '''위치 트리'''^[20])는 각 정점의 자식에 대한 순서가 지정된 뿌리 트리이다.^[21] 자식의 순서가 평면에 트리를 임베딩하는 것과 같고, 루트가 위에 있고 각 정점의 자식은 해당 정점보다 아래에 있기 때문에 "평면 트리"라고 한다. 평면에 뿌리 트리를 임베딩하면 자식의 방향을 고정하여 순서를 제공한다. 반대로, 순서 트리가 주어지고 루트를 위에 그리면 순서 트리의 자식 정점은 왼쪽에서 오른쪽으로 그려져 고유한 평면 임베딩을 생성한다.

4. 1. 유향 그래프

일반적으로 무향 나무는 임의의 점을 뿌리로 간주할 수 있다. 이에 반해 유향 나무는 뿌리인 점을 단 하나만 갖는다. 변의 방향은 뿌리에서 잎으로 향하는 경우와 잎에서 뿌리로 향하는 경우가 있다. 혼합은 불가능하다 (혼합되면 사이클이 생겨버린다).^[23]

사이클을 갖지 않는 임의의 유향 그래프는 유향 비순환 그래프(DAG)^[24]이다. 유향 나무는 연결된 유향 비순환 그래프이기도 하지만, 연결된 유향 비순환 그래프가 반드시 유향 나무인 것은 아니다 (DAG에서는 자손 또는 부모의 공유가 있는 경우가 있어 나무가 아닐 수 있다).

4. 2. 루트 트리 (Rooted Tree)

루트 트리(rooted tree)는 하나의 정점을 루트(root)로 지정한 트리이다.^[19] 루트 트리의 간선에는 자연스러운 방향을 부여할 수 있는데, 루트에서 멀어지거나 루트를 향하는 방향이 있다. 이때 방향이 있는 루트 트리가 된다. 루트에서 멀어지는 방향을 가질 때는 ''아보레스cent'' 또는 ''아웃 트리''라고 하며, 루트를 향하는 방향을 가질 때는 ''안티 아보레스cent'' 또는 ''인 트리''라고 한다.

어떤 노드를 선택하여 그것을 가장 "위에" 있다고 생각하면, 그 노드를 기준으로 두 노드 간에 상하 관계를 고려할 수 있다(모든 노드의 조합에 대해 정의되지 않을 수 있다). 이때, 그 가장 위에 있는 노드를 '''루트'''(root)라고 한다. 루트를 가진 트리를 단순히 트리와 구별하여 '''근원 트리'''라고 한다.

근원 트리에 관한 용어는 가계도에 비유하여 사용되는 경우가 많다.

점 과 가 변으로 연결되어 있으며, 이 보다 루트에 가까울 때, 은 의 '''부모'''라고 하며, 는 의 '''자식'''이라고 한다.
점 와 이 공통의 부모를 가질 때, 와 은 '''형제'''라고 한다.
근원 트리 상의 두 점 , 에 대해, 와 루트를 잇는 경로 상에 이 있을 때, 은 의 '''선조'''라고 하며, 는 의 '''자손'''이라고 한다.

또한, 근원 트리에 관한 용어로서, 그 외에 다음과 같은 것들이 있다.

자식을 갖지 않는 점을 '''잎'''이라고 한다.
각 변의 길이를 1로 할 때, 점과 루트 간의 경로의 길이를 그 점의 '''높이'''라고 한다. 또한, 루트로부터 가장 경로의 길이가 길어지는 점까지의 길이를, 그 트리의 '''높이'''라고 한다.

루트 트리에서 정점 의 ''부모''는 루트로 가는 경로에서 에 연결된 정점이며, 모든 정점은 고유한 부모를 가지며 루트는 부모가 없다. 정점 의 ''자식''은 가 부모인 정점이다. 정점 의 ''조상''은 의 부모이거나 (재귀적으로) 의 부모의 조상인 정점이다. 정점 의 ''자손''은 의 자식이거나 (재귀적으로) 의 자식의 자손인 정점이다. 정점 의 ''형제''는 와 부모를 공유하는 트리상의 다른 정점이다. ''리프''는 자식이 없는 정점이다. ''내부 정점''은 리프가 아닌 정점이다.

루트 트리에서 정점의 ''높이''는 해당 정점에서 리프까지의 가장 긴 하향 경로의 길이이다. 트리의 ''높이''는 루트의 높이이다. 정점의 ''깊이''는 루트(''루트 경로'')까지의 경로의 길이이다. 트리의 깊이는 모든 정점의 최대 깊이이다. 깊이는 특히 다양한 자체 균형 트리, 특히 AVL 트리를 조작하는 데 일반적으로 필요하다. 루트의 깊이는 0이고, 리프의 높이는 0이며, 단일 정점만 있는 트리(따라서 루트와 리프 모두)의 깊이와 높이는 0이다. 일반적으로, 빈 트리(허용되는 경우 정점이 없는 트리)의 깊이와 높이는 −1이다.

자연수 에 대해, 잎이 아닌 각 점에 대해 해당 점의 자식 수가 항상 인 나무를 '''분 나무'''(분기; n-ary tree)라고 한다. 특히 이진 트리는 여러 알고리즘과 밀접하게 관련된 자료 구조이다(단, 대부분은 다음에 설명할 유향 트리에 의한 이진 트리이다).

''-진 트리''(음이 아닌 정수 )는 각 정점이 최대 개의 자식을 갖는 루트 트리이다.^[19] 2-진 트리는 종종 ''이진 트리''라고 하며, 3-진 트리는 때때로 ''삼진 트리''라고 한다.

'''순서 트리''' (또는 '''평면 트리''' 또는 '''위치 트리'''^[20])는 각 정점의 자식에 대한 순서가 지정된 뿌리 트리이다.^[21] 이는 자식의 순서가 평면에 트리를 임베딩하는 것과 같고, 루트가 위에 있고 각 정점의 자식은 해당 정점보다 아래에 있기 때문에 "평면 트리"라고 한다. 평면에 뿌리 트리를 임베딩하면 자식의 방향, 예를 들어 왼쪽에서 오른쪽으로 고정하면 임베딩은 자식의 순서를 제공한다. 반대로, 순서 트리가 주어지고 관례적으로 루트를 위에 그리면 순서 트리의 자식 정점은 왼쪽에서 오른쪽으로 그려져 본질적으로 고유한 평면 임베딩을 생성할 수 있다.

5. 역사

케일리 공식은 1860년에 카를 빌헬름 보르하르트(Carl Wilhelm Borchardt|카를 빌헬름 보르하르트^de, 1817~1880)가 최초로 증명하였다.^[26] 1889년에 아서 케일리가 같은 정리의 새 증명을 발표하였다.^[27] 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.

에른스트 파울 하인츠 프뤼퍼(Ernst Paul Heinz Prüfer|에른스트 파울 하인츠 프뤼퍼^de, 1896~1934)는 1918년에 프뤼퍼 열을 도입하여 케일리 공식에 대한 다른 증명을 제시하였다.^[28]

참조

_[1] 논문
_[2] 논문
_[3] 논문
_[4] 논문
_[5] 서적 Combinatorics for Computer Science Courier Dover Publications
_[6] 서적 Graph Theoretic Methods in Multiagent Networks Princeton University Press
_[7] 서적 Design and Analysis of Approximation Algorithms Springer Science & Business Media
_[8] 서적 Handbook of Graph Theory, Second Edition CRC Press
_[9] 서적 Combinatorial Optimization: Theory and Algorithms Springer Science & Business Media
_[10] 서적 Algorithms and Data Structures: The Basic Toolbox http://people.mpi-in[...] Springer Science & Business Media 2008
_[11] 서적 Sets, Logic and Maths for Computing Springer Science & Business Media
_[12] 서적 Discrete Mathematics and Its Applications, 7th edition McGraw-Hill Science
_[13] 서적 Combinatorial Optimization: Polyhedra and Efficiency Springer
_[14] 간행물 "On the theory of the analytical forms called trees," https://books.google[...] 1857
_[15] arXiv Spanning trees with few branch vertices 2019-10-09
_[16] journal On directed trees and directed {{mvar|k}}-trees of a digraph and their generation
_[17] journal Complexes of directed trees
_[18] 간행물 Estimating a directed tree for extremes 2024-02
_[19] 웹사이트 k-ary tree http://xlinux.nist.g[...] U.S. National Institute of Standards and Technology 2007-05-04
_[20] 서적 Introduction to Algorithms https://mitpress.mit[...] MIT Press 2022
_[21] 간행물 Enumerative Combinatorics, Vol. I https://books.google[...] Cambridge University Press
_[22] 논문
_[23] 문서
_[24] 문서
_[25] 저널 케일리 공식의 네 가지 증명 http://society.kisti[...] 2008-08
_[26] 저널 https://archive.org/[...]
_[27] 저널
_[28] 저널

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com